package cn.lastwhisper.leetcode.dynamic.完全平方数_279_中等;

class Solution1 {
    /**
     * 题目地址：https://leetcode-cn.com/problems/perfect-squares/
     * -------------------------------------------------------------------
     * 思考：
     * -------------------------------------------------------------------
     * 思路：
     *  四平方定理：每个正整数均可表为四个整数的平方和(其中有些整数可以为零)，满足n=(4^a)*(8b+7)
     *      1、任何正整数都可以拆分成不超过4个数的平方和 ---> 答案只可能是1,2,3,4
     *      2、如果一个数正好可以拆成4个数的平方和，则这个数还满足 n = (4^a)*(8b+7) --->
     *          因此可以先看这个数是否满足上述公式，如果不满足，答案就是1,2,3了
     *      3、如果这个数本来就是某个数的平方，那么答案就是1，否则答案就只剩2,3了
     *      4、如果答案是2，即n=a^2+b^2，那么我们可以枚举a，来验证，如果验证通过则答案是2
     *      5、只能是3
     * -------------------------------------------------------------------
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     */
    public int numSquares(int n) {
        // 1、如果n可以拆成四个数的平方，n=(4^a)*(8b+7)
        while (n % 4 == 0) {
            n /= 4;
        }
        if (n % 8 == 7) {
            return 4;
        }
        /*
         * 2、如果n本来就是某个数的平方，那么答案就是1
         * 3、如果答案是2，即n=a^2+b^2，那么我们可以枚举a，来验证，如果验证通过则答案是2
         */
        int a = 0,b;
        while ((a * a) < n) {
            b = (int) Math.sqrt(n - (a * a));
            if ((a * a) + (b * b) == n) {
                if (a != 0 && b != 0) {
                    return 2;
                } else {
                    return 1;
                }
            }
            a++;
        }
        // 4、否则为3
        return 3;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1().numSquares(12));
        System.out.println(new Solution1().numSquares(13));
    }
}